/*
 * GeneticAlgorithm.h
 *
 *  Created on: Oct 21, 2013
 *      Author: filipe
 */

#ifndef GENETICALGORITHM_H_
#define GENETICALGORITHM_H_

#include <float.h>
#include <cstdlib>
#include <cstring>
#include "GeneticAlgorithmParameters.h"
#include "GeneticAlgorithmAdvancedParameters.h"

namespace EvolutionaryOptimization
{
	template<class T>
	class GeneticAlgorithm
	{
		protected:

			T **_Elite;
			T **_Population;
			T **_NewPopulation; // buffer for fast population creation
			int _CurrentGeneration;
			double *_PopulationFitness;
			double *_EliteFitness;

			GeneticAlgorithmParameters *_Params;
			GeneticAlgorithmAdvancedParameters<T> *_AdvancedParams;

			double (*_FitnessFunction) (T *Individual);

			void _GenericConstructor()
			{
				_AllocateElite();
				_AllocatePopulation();
				_InitializeElite();

				srand(time(NULL));

				_CurrentGeneration = 0;
			}

			void _AllocatePopulation()
			{
				_Population = (T**) calloc (_Params->GetPopulationSize(), sizeof(T*));
				_NewPopulation = (T**) calloc (_Params->GetPopulationSize(), sizeof(T*));
				_PopulationFitness = (double *) calloc (_Params->GetPopulationSize(), sizeof(double));

				for (int i = 0; i < _Params->GetPopulationSize(); i++)
				{
					_Population[i] = (T*) calloc (_Params->GetDimension(), sizeof(T));
					_NewPopulation[i] = (T*) calloc (_Params->GetDimension(), sizeof(T));
				}
			}

			void _AllocateElite()
			{
				_Elite = (T**) calloc (_Params->GetEliteSize(), sizeof(T*));
				_EliteFitness = (double *) calloc (_Params->GetEliteSize(), sizeof(double));

				for (int i = 0; i < _Params->GetEliteSize(); i++)
				{
					_Elite[i] = (T*) calloc (_Params->GetDimension(), sizeof(T));
				}
			}

			void _InitializeElite()
			{
				for (int i = 0; i < _Params->GetEliteSize(); i++)
				{
					_EliteFitness[i] = -DBL_MAX;
				}
			}

			void _DeallocateElite()
			{
				for (int i = 0; i < _Params->GetEliteSize(); i++)
				{
					free(_Elite[i]);
				}

				free(_Elite);
				free(_EliteFitness);
			}

			void _DeallocatePopulation()
			{
				for (int i = 0; i < _Params->GetPopulationSize(); i++)
				{
					free(_Population[i]);
					free(_NewPopulation[i]);
				}

				free(_Population);
				free(_NewPopulation);
				free(_PopulationFitness);
			}

			void _EvaluateFitnessFunction()
			{
				// TODO: Add openmp flags here!
				for (int i = 0; i < _Params->GetPopulationSize(); i++)
				{
					_PopulationFitness[i] = (*_FitnessFunction)(_Population[i]);
				}
			}

			void _SaveElite()
			{
				int i, j, k;

				// find the best individuals
				for (i = 0; i < _Params->GetPopulationSize(); i++)
				{
					for (j = 0; j < _Params->GetEliteSize(); j++)
					{
						if (_PopulationFitness[i] > _EliteFitness[j])
						{
							// open space for the new individual
							for (k = (_Params->GetEliteSize() - 1); k > j; k--)
							{
								memcpy(_Elite[k], _Elite[k - 1], _Params->GetDimension() * sizeof(T));
								_EliteFitness[k] = _EliteFitness[k - 1];
							}

							memcpy(_Elite[j], _Population[i], _Params->GetDimension() * sizeof(T));
							_EliteFitness[j] = _PopulationFitness[i];
						}
					}
				}
			}

			void _CheckBoundaries(T *individual)
			{
				for (int i = 0; i < _Params->GetDimension(); i++)
				{
					if (individual[i] < _Params->GetMinValue(i))
						individual[i] = _Params->GetMinValue(i);

					if (individual[i] > _Params->GetMaxValue(i))
						individual[i] = _Params->GetMaxValue(i);
				}
			}

			int _ItsTimeForMutation()
			{
				double probability = ((double) rand()) / ((double) RAND_MAX);

				if (probability < _AdvancedParams->GetMutationProbability())
					return 1;
				else
					return 0;
			}

			int _ItsTimeForCrossover()
			{
				double probability = ((double) rand()) / ((double) RAND_MAX);

				if (probability < _AdvancedParams->GetCrossoverProbability())
					return 1;
				else
					return 0;
			}

			void _CreateNewPopulation()
			{
				Parents p;

				_SaveElite();

				_AdvancedParams->GetSelector()->InitializeSelector(_PopulationFitness);

				for (int i = 0; i < (_Params->GetPopulationSize() / 2); i += 2)
				{
					p = _AdvancedParams->GetSelector()->GetNextParents();

					memcpy(_NewPopulation[i], _Population[p.GetParents().first], _Params->GetDimension() * sizeof(T));
					memcpy(_NewPopulation[i + 1], _Population[p.GetParents().second], _Params->GetDimension() * sizeof(T));

					if (_ItsTimeForCrossover())
					{
						_AdvancedParams->GetCrossover()->PerformCrossover(_NewPopulation[i], _NewPopulation[i + 1]);
					}

					if (_ItsTimeForMutation())
					{
						_AdvancedParams->GetMutation()->PerformMutation(_NewPopulation[i]);
					}

					if (_ItsTimeForMutation())
					{
						_AdvancedParams->GetMutation()->PerformMutation(_NewPopulation[i + 1]);
					}

					_CheckBoundaries(_NewPopulation[i]);
					_CheckBoundaries(_NewPopulation[i + 1]);
				}

				// make the population be the new population and save
				// the population pointer as the new population pointer
				T **aux = _Population;
				_Population = _NewPopulation;
				_NewPopulation = aux;

				_CurrentGeneration++;
			}

			// TODO: trocar o nome desse metodo para CondicaoDeParada ao inves de Convergencia
			int _CheckForConvergence()
			{
				// TODO: Adicionar os outros criterios de parada
				if (_CurrentGeneration >= _AdvancedParams->GetNumMaxGenerations())
					return 1;
				else
					return 0;
			}

		public:

			GeneticAlgorithm(GeneticAlgorithmParameters *params)
			{
				_Params = params;
				_GenericConstructor();
			}

			GeneticAlgorithm(GeneticAlgorithmParameters *params, GeneticAlgorithmAdvancedParameters<T> *advanced_params)
			{
				_Params = params;
				_AdvancedParams = advanced_params;
				_GenericConstructor();
			}

			virtual ~GeneticAlgorithm()
			{
				delete(_Params);
				delete(_AdvancedParams);

				_DeallocateElite();
				_DeallocatePopulation();
			}

			virtual void Optimize(double (*fitness_function)(T *individual))
			{
				// check if this is the best method to pass the function
				_FitnessFunction = fitness_function;

				_EvaluateFitnessFunction();

				while (!_CheckForConvergence())
				{
					_CreateNewPopulation();
					_EvaluateFitnessFunction();
				}
			}

			virtual T* GetBestIndividual() const
			{
				int i;
				T *best_individual = NULL;
				double best_individual_fitness = -DBL_MAX;

				for (i = 0; i < _Params->GetPopulationSize(); i++)
				{
					if (_PopulationFitness[i] > best_individual_fitness)
					{
						best_individual = _Population[i];
						best_individual_fitness = _PopulationFitness[i];
					}
				}

				for (i = 0; i < _Params->GetEliteSize(); i++)
				{
					if (_EliteFitness[i] > best_individual_fitness)
					{
						best_individual = _Elite[i];
						best_individual_fitness = _EliteFitness[i];
					}
				}

				/* TODO: Store the best individual fitness and make a method to recover it */

				return best_individual;
			}

			// checar por que nao consegui colocar esse metodo no constructor e sobrescrever na classe filha
			virtual void _GenerateInitialPopulation() = 0;
	};
}

#endif
